package leetcode.editor.cn.q1_300.q250;
//给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。 
//
// 叶子节点 是指没有子节点的节点。 
//
// 示例 1： 
// 
// 
//输入：root = [1,2,3,null,5]
//输出：["1->2->5","1->3"]
// 
//
// 示例 2： 
//
// 
//输入：root = [1]
//输出：["1"]
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目在范围 [1, 100] 内 
// -100 <= Node.val <= 100 
// 
//
// 👍 970 👎 0

import leetcode.editor.cn.util.tree.btree.BTreeUtil;
import leetcode.editor.cn.util.tree.btree.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Q257_BinaryTreePaths {
    //leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        public List<String> binaryTreePaths(TreeNode root) {
            List<String> routes = new ArrayList<>();

            Deque<TreeNode> q1 = new ArrayDeque<>();
            Deque<String> q2 = new ArrayDeque<>();

            q1.add(root);
            q2.add(String.valueOf(root.val));

            while (!q1.isEmpty()) {
                TreeNode node = q1.poll();
                String val = q2.poll();
                if (node.left == null && node.right == null) {
                    routes.add(val);
                } else {
                    if (node.left != null) {
                        q1.add(node.left);
                        q2.add(val + "->" + node.left.val);
                    }
                    if (node.right != null) {
                        q1.add(node.right);
                        q2.add(val + "->" + node.right.val);
                    }
                }
            }

            return routes;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q257_BinaryTreePaths().new Solution();
        // TO TEST
        System.out.println(solution.binaryTreePaths(BTreeUtil.generateFromArr(1, 2, 3, null, 5)));
        System.out.println(solution.binaryTreePaths(BTreeUtil.generateFromArr(1)));
    }
}